package main

func main() {

	println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
	println(maxProfit([]int{7, 6, 4, 3, 1}))

}

func maxProfit(prices []int) int {

	// 动态规划核心思想：若前一个元素大于0，则将其加到当前元素上
	/*
		假设前一天的利润为 f(i-1)
		第i天的利润为f(i)
		如果当天利润 < 0 ,则重新计算利润
		分析：7, 1, 5, 3, 6, 4
		f(0): 利润为0,最大利润0 。f(i-1)<0 则取0
		f(1): f(0)利润为0，当前利润 1-7 + max(0, f(0))= -6 ， 最大利润0。
		f(2): f(1)利润为-6,当前利润 5-1 + max(0,f(1)) = 4 , 最大利润 4。
		f(3): f(2)利润为4， 当前利润 3-5 + max(0,f(2)) = 2 , 最大利润4。
		f(4): f(3)利润为2，当前利润为 6-3 + max(0,f(3)) = 5。最大利润为5.
		f(5): f(4)利润为5，当前利润为 4-6 + max(0,f(4)) = 3，最大利润 5

		算法实现：初始化 f(0) = 0， 最大利润maxProfit = 0
		1. 前一天的利润：f(i-1) = pre, 初始化为0
		2. 当前利润 f(i) = prices[i] - prices[i-1] + max(0, pre)
		3. 比较f(i) 和 maxProfit , 按需更新maxProfit

	*/

	maxProfit := 0

	// 初始化 f(0)
	pre := 0

	for i := 1; i < len(prices); i++ {

		// 计算当前利润: max(0,f(1))
		if pre < 0 {
			pre = 0
		}

		nowProfit := prices[i] - prices[i-1] + pre
		if nowProfit > maxProfit {
			maxProfit = nowProfit
		}

		pre = nowProfit

	}

	return maxProfit
}
